SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Proximal gradient method</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Proximal gradient method</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p><b>Proximal gradient methods</b> are a generalized form of projection used to solve non-differentiable <a href="Convex_optimization" title="Convex optimization">convex optimization</a> problems.

</p>

<p>Many interesting problems can be formulated as convex optimization problems of the form

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \min _{\mathbf {x} \in \mathbb {R} ^{d}}\sum _{i=1}^{n}f_{i}(\mathbf {x} )}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{\mathbf {x} \in \mathbb {R} ^{d}}\sum _{i=1}^{n}f_{i}(\mathbf {x} )}</annotation>

</semantics>

</math></span><img src="./00426c35392cab5dc626048f671635f6db970a98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:13.431ex; height:6.843ex;" alt="{\displaystyle \min _{\mathbf {x} \in \mathbb {R} ^{d}}\sum _{i=1}^{n}f_{i}(\mathbf {x} )}" loading="lazy"></span>

</p><p>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{i}:\mathbb {R} ^{d}\rightarrow \mathbb {R} ,\ i=1,\dots ,n}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{i}:\mathbb {R} ^{d}\rightarrow \mathbb {R} ,\ i=1,\dots ,n}</annotation>

</semantics>

</math></span><img src="./7e4024b70721c2bdc418fd95b92ad302366ea0bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:25.189ex; height:3.009ex;" alt="{\displaystyle f_{i}:\mathbb {R} ^{d}\rightarrow \mathbb {R} ,\ i=1,\dots ,n}" loading="lazy"></span> are possibly non-differentiable <a href="Convex_functions" class="mw-redirect" title="Convex functions">convex functions</a>. The lack of differentiability rules out conventional smooth optimization techniques like the <a href="Gradient_descent" title="Gradient descent">steepest descent method</a> and the <a href="Conjugate_gradient_method" title="Conjugate gradient method">conjugate gradient method</a>, but proximal gradient methods can be used instead.

</p><p>Proximal gradient methods starts by a splitting step, in which the functions <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{1},...,f_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{1},...,f_{n}}</annotation>

</semantics>

</math></span><img src="./56add4996a8ffb2d648fd1b373476afd13c2a117.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.721ex; height:2.509ex;" alt="{\displaystyle f_{1},...,f_{n}}" loading="lazy"></span> are used individually so as to yield an easily <a href="https://en.wiktionary.org/wiki/implementable" class="extiw external" title="wikt:implementable">implementable</a> algorithm. They are called <a href="Proximal" class="mw-redirect" title="Proximal">proximal</a> because each non-differentiable function among <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{1},...,f_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{1},...,f_{n}}</annotation>

</semantics>

</math></span><img src="./56add4996a8ffb2d648fd1b373476afd13c2a117.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.721ex; height:2.509ex;" alt="{\displaystyle f_{1},...,f_{n}}" loading="lazy"></span> is involved via its <a href="Proximal_operator" title="Proximal operator">proximity operator</a>. Iterative shrinkage thresholding algorithm,<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> <a href="Landweber_iteration" title="Landweber iteration">projected Landweber</a>, projected gradient, <a href="Alternating_projection" class="mw-redirect" title="Alternating projection">alternating projections</a>, <a href="Alternating_direction_method_of_multipliers" class="mw-redirect" title="Alternating direction method of multipliers">alternating-direction method of multipliers</a>, alternating

split <a href="Bregman_method" title="Bregman method">Bregman</a> are special instances of proximal algorithms.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>For the theory of proximal gradient methods from the perspective of and with applications to <a href="Statistical_learning_theory" title="Statistical learning theory">statistical learning theory</a>, see <a href="Proximal_gradient_methods_for_learning" title="Proximal gradient methods for learning">proximal gradient methods for learning</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Projection_onto_convex_sets_(POCS)">Projection onto convex sets (POCS)</h2></div>

<p>One of the widely used convex optimization algorithms is <a href="Projections_onto_convex_sets" title="Projections onto convex sets">projections onto convex sets</a> (POCS). This algorithm is employed to recover/synthesize a signal satisfying simultaneously several convex constraints. Let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{i}}</annotation>

</semantics>

</math></span><img src="./65da883ca3d16b461e46c94777b0d9c4aa010e79.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.939ex; height:2.509ex;" alt="{\displaystyle f_{i}}" loading="lazy"></span> be the indicator function of non-empty closed convex set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{i}}</annotation>

</semantics>

</math></span><img src="./cc49dc02c0ec8c86b67e7d10518ac791eda0bf22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.461ex; height:2.509ex;" alt="{\displaystyle C_{i}}" loading="lazy"></span> modeling a constraint. This reduces to convex feasibility problem, which require us to find a solution such that it lies in the intersection of all convex sets <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{i}}</annotation>

</semantics>

</math></span><img src="./cc49dc02c0ec8c86b67e7d10518ac791eda0bf22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.461ex; height:2.509ex;" alt="{\displaystyle C_{i}}" loading="lazy"></span>. In POCS method each set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{i}}</annotation>

</semantics>

</math></span><img src="./cc49dc02c0ec8c86b67e7d10518ac791eda0bf22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.461ex; height:2.509ex;" alt="{\displaystyle C_{i}}" loading="lazy"></span> is incorporated by its <a href="Projection_operator" class="mw-redirect" title="Projection operator">projection operator</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{C_{i}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{C_{i}}}</annotation>

</semantics>

</math></span><img src="./cb3edbdaf615c986290091e3ad14f62aa95d4e16.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.524ex; height:2.843ex;" alt="{\displaystyle P_{C_{i}}}" loading="lazy"></span>. So in each <a href="Iteration" title="Iteration">iteration</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> is updated as

</p>

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{k+1}=P_{C_{1}}P_{C_{2}}\cdots P_{C_{n}}x_{k}}</annotation>

</semantics>

</math></span><img src="./29a13073423bc5f78a958db509856876a8074fff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:24.86ex; height:2.843ex;" alt="{\displaystyle x_{k+1}=P_{C_{1}}P_{C_{2}}\cdots P_{C_{n}}x_{k}}" loading="lazy"></span></dd></dl>

<p>However beyond such problems <a href="Projection_operator" class="mw-redirect" title="Projection operator">projection operators</a> are not appropriate and more general operators are required to tackle them. Among the various generalizations of the notion of a convex projection operator that exist, proximal operators are best suited for other purposes.

</p>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<p>Special instances of Proximal Gradient Methods are

</p>

<ul><li><a href="Landweber_iteration" title="Landweber iteration">Projected Landweber</a></li>

<li><a href="Alternating_projection" class="mw-redirect" title="Alternating projection">Alternating projection</a></li>

<li><a href="Alternating_direction_method_of_multipliers" class="mw-redirect" title="Alternating direction method of multipliers">Alternating-direction method of multipliers</a></li></ul>

<ul><li><a href="Proximal_operator" title="Proximal operator">Proximal operator</a></li>

<li><a href="Proximal_gradient_methods_for_learning" title="Proximal gradient methods for learning">Proximal gradient methods for learning</a></li>

<li><a href="Frank%E2%80%93Wolfe_algorithm" title="Frank–Wolfe algorithm">Frank–Wolfe algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFDaubechiesDefriseDe_Mol2004" class="citation journal cs1">Daubechies, I; Defrise, M; <a href="Christine_De_Mol" title="Christine De Mol">De Mol, C</a> (2004). "An iterative thresholding algorithm for linear inverse problems with a sparsity constraint". <i>Communications on Pure and Applied Mathematics</i>. <b>57</b> (11): <span class="nowrap">1413–</span>1457. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/0307152">math/0307152</a></span>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2003math......7152D">2003math......7152D</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fcpa.20042">10.1002/cpa.20042</a>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">Details of proximal methods are discussed in <cite id="CITEREFCombettesPesquet2009" class="citation arxiv cs1">Combettes, Patrick L.; Pesquet, Jean-Christophe (2009). "Proximal Splitting Methods in Signal Processing". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/0912.3522">0912.3522</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.OC">math.OC</a>].</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFRockafellar1970" class="citation book cs1"><a href="R._Tyrrell_Rockafellar" title="R. Tyrrell Rockafellar">Rockafellar, R. T.</a> (1970). <i>Convex analysis</i>. Princeton: Princeton University Press.</cite></li>

<li><cite id="CITEREFCombettesPesquet2011" class="citation book cs1">Combettes, Patrick L.; Pesquet, Jean-Christophe (2011). <i>Fixed-Point Algorithms for Inverse Problems in Science and Engineering</i>. Vol. 49. pp. <span class="nowrap">185–</span>212.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li>Stephen Boyd and Lieven Vandenberghe Book, <a rel="nofollow" class="external text" href="https://web.stanford.edu/~boyd/cvxbook/"><i>Convex optimization</i></a></li>

<li><a rel="nofollow" class="external text" href="https://web.stanford.edu/class/ee364a/">EE364a: Convex Optimization I</a> and <a rel="nofollow" class="external text" href="https://web.stanford.edu/class/ee364b/">EE364b: Convex Optimization II</a>, Stanford course homepages</li>

<li><a rel="nofollow" class="external text" href="https://people.eecs.berkeley.edu/~elghaoui/Teaching/EE227A/lecture18.pdf">EE227A: Lieven Vandenberghe Notes</a> Lecture 18</li>

<li><a rel="nofollow" class="external text" href="https://github.com/kul-forbes/ProximalOperators.jl">ProximalOperators.jl</a>: a <a href="Julia_(programming_language)" title="Julia (programming language)">Julia</a> package implementing proximal operators.</li>

<li><a rel="nofollow" class="external text" href="https://github.com/kul-forbes/ProximalAlgorithms.jl">ProximalAlgorithms.jl</a>: a <a href="Julia_(programming_language)" title="Julia (programming language)">Julia</a> package implementing algorithms based on the proximal operator, including the proximal gradient method.</li>

<li><a rel="nofollow" class="external text" href="http://proximity-operator.net/">Proximity Operator repository</a>: a collection of proximity operators implemented in <a href="Matlab" class="mw-redirect" title="Matlab">Matlab</a> and <a href="Python_(programming_language)" title="Python (programming language)">Python</a>.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-21" href="https://en.wikipedia.org/wiki/?title=Proximal_gradient_method&oldid=1296664511">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>